/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec 困难
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
 * 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 * 注意：
 * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
 * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
 * 输入：s = "ADOBECODEBANC", t = "ABC"
 * 输出："BANC"
 * 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
 * @since 2023-09-06 21:01
 */
public class _076最小覆盖子串 {
    public static void main(String[] args) {
//        String s = "ADOBECODEBANC", t = "ABC";
        String s = "a", t = "aa";
        System.out.println(new _076最小覆盖子串().minWindow(s, t));
    }
    //大写
    int[] hash1 = new int[26];
    //小写
    int[] hash2 = new int[26];
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";
        //记录t中出现的字符
        for (char c : t.toCharArray()) {
            if (c >= 'a') {
                hash2[c - 'a']++;
            } else {
                hash1[c - 'A']++;
            }
        }
        //双指针
        int l = 0, r = 0;
        int ansLeft = 0, minLen = Integer.MAX_VALUE;
        //区间需要包含的字符数
        int cnt = t.length();
        while (r < s.length()) {
            boolean res = decr(s.charAt(r));
            if (res) cnt--; //s.charAt(r) 为一个需要的字符
            while (cnt <= 0) {    //包含t, 不断移动左指针，找最短
                if (r - l + 1 < minLen) {
                    ansLeft = l;
                    minLen = r - l + 1;
                }
                res = incr(s.charAt(l));
                if (res) cnt++; //s.charAt(r) 为一个需要的字符
                l++;
            }
            //移动右指针
            r++;
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(ansLeft, ansLeft + minLen);
    }

    /**
     * 移动左指针，将其字符对应hash值+1
     * @return c 为 需要包含的t中字符 返回false,否则返回true
     */
    private boolean incr(char c) {
        if (c >= 'a') {
            hash2[c - 'a']++;
            return hash2[c - 'a'] > 0;
        } else {
            hash1[c - 'A']++;
            return hash1[c - 'A'] > 0;
        }
    }

    /**
     * 移动右指针，将其字符对应hash值-1
     * @return c 为 需要包含的t中字符 返回true,否则返回false
     */
    private boolean decr(char c) {
        if (c >= 'a') {
            hash2[c - 'a']--;
            return hash2[c - 'a'] >= 0;
        } else {
            hash1[c - 'A']--;
            return hash1[c - 'A'] >= 0;
        }
    }
}
